#include "quadtree.h"

cQuadTree::cQuadTree(TreeNode* pRoot)
{
	m_pRoot = pRoot;
}
cQuadTree::~cQuadTree()
{
	DeleteTree(m_pRoot);
}
void cQuadTree::GenerateTree(TreeNode* node,int rows,int cols,float width,float depth,vec3 center)
{
	node->rows = rows;
	node->cols = cols;
	node->width = width;
	node->depth = depth;
	node->center = center;
	if(rows<=DEFAULTROWS&&cols<=DEFAULTCOLS){
		for(int i = 0;i<4;++i){
			node->Child[i] = NULL;
		}
		return;
	}
	rows = rows/2 + 1;
	cols = cols/2 + 1;
	width/=2;
	depth/=2;
	for(int i = 0;i<4;++i){
		node->Child[i] = new TreeNode;
		node->Child[i]->pParent = node;
	}
	GenerateTree(node->Child[0],rows,cols,width,depth,vec3(center.x - width/2,center.y,center.z + depth/2));
	GenerateTree(node->Child[1],rows,cols,width,depth,vec3(center.x + width/2,center.y,center.z + depth/2));
	GenerateTree(node->Child[2],rows,cols,width,depth,vec3(center.x + width/2,center.y,center.z - depth/2));
	GenerateTree(node->Child[3],rows,cols,width,depth,vec3(center.x - width/2,center.y,center.z - depth/2));
}

void cQuadTree::DeleteTree(TreeNode* node)
{
	if(node->Child[0]==NULL&&node->Child[1]==NULL&&
	   node->Child[2]==NULL&&node->Child[3]==NULL)
	{
		delete node;
		node = NULL;
		return;     
	}
	for(int i = 0;i<4;++i)
	{
		DeleteTree(node->Child[i]);
	}
}